package practice2;

import utils.node.DoubleNode;
import utils.NodeUtils;

/**
 * @author Tara
 * @implNote 给定一个双向链表，删除所有节点值为x的节点，并返回头节点head
 */
public class Pra4 {

    public static void main(String[] args) {
        Object[] arr = {3, 2, 4, 7, 9, 3, 3, 2, 3, 23, 21};
        // 构造一个链表
        DoubleNode node = NodeUtils.constructDoubleNode(arr);
        // 打印链表轨迹
        NodeUtils.printDoubleNode(node);
        NodeUtils.printDoubleNode2(node);
        // 移除所有值为3的节点
        DoubleNode removedNode = removeValues(node, 2);
        //打印链表结构
        NodeUtils.printDoubleNode(removedNode);
        NodeUtils.printDoubleNode2(removedNode);
    }

    /**
     * 移除单向链表的值为xx的节点
     * @param head 双链表的一个头部
     * @param value 要移除节点的值value；
     * @return 新头部节点newHead
     */
    private static DoubleNode removeValues(DoubleNode head, Object value) {
        // 1.考虑head第一位是否存在要移除的节点
        while (null != head) {
            // 先排除head位置存在要移除的节点
            if (head.value != value) {
                // 首位没有符合条件的就停止。
                break;
            }
            head = head.nextNode;
            //指针后移后，上一个指针置空；
            head.lastNode = null;
        }
        // 2.考虑 中间是否存在要移除的节点，存在就跳过去，不存在指针指向下一个
        // 游标指向当前节点
        DoubleNode cur = head;
        DoubleNode pre = null;
        DoubleNode next = null;
        while (null != cur) {
            // 记录指针的下一节点
            next = cur.nextNode;
            if (cur.value == value) {
                // 直接将当前节点指向下一节点，跳过cur；
                pre.nextNode = next;
                // 释放当前节点的指向
                cur.nextNode = null;
                cur.lastNode = null;
                // 让下一个节点往回指；
                next.lastNode = pre;
            } else {
                // 当前节点变为下一次的pre节点
                pre = cur;
            }
            //游标后移
            cur = next;
        }
        return head;
    }
}
